package real.ZSBank;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Factory {
    //1.给定一个A工厂的加工顺序如123，B工厂可以随时取出进行加工，取出顺序为先加工的后取（栈），然后求B工厂可能的加工顺序（123，132，231，213，321）
    public static List<List<Integer>> getOrders(List<Integer> input) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(input, new Stack<>(), new ArrayList<>(), result);
        return result;
    }

    private static void dfs(List<Integer> queue, Stack<Integer> stack, List<Integer> path, List<List<Integer>> result) {
        if (queue.isEmpty() && stack.isEmpty()) {
            result.add(new ArrayList<>(path));
            return;
        }
        // 入栈操作
        if (!queue.isEmpty()) {
            Integer first = queue.get(0);
            List<Integer> nextQueue = queue.subList(1, queue.size());
            stack.push(first);
            dfs(nextQueue, stack, path, result);
            stack.pop();
        }
        // 出栈操作
        if (!stack.isEmpty()) {
            Integer top = stack.pop();
            path.add(top);
            dfs(queue, stack, path, result);
            path.remove(path.size() - 1);
            stack.push(top);
        }
    }
    public static void main(String[] args) {
        ArrayList<Integer> input = new ArrayList<>();
        List<List<Integer>> orders = getOrders(input);
        for (List<Integer> order : orders) {
            System.out.println(order);
        }
    }
}
